package za.org.meraka.mu;
import java.util.List;
import java.util.ArrayList;
import java.util.StringTokenizer;

//
// there are 3 techniques for calculating similarities
//
// 1 - calculated the ngrams from the second string only
// 2 - calculate even weighted
//
public class Ngram
{



    public Ngram() 
    {
    }

    public static double getSimilarity(int method, String wordOne, String wordTwo, int n)
    {
        List<NgramResult> res1 = processString(wordOne, n);
	System.out.println("first results has " + res1.size());
        displayResult(res1);

        List<NgramResult> res2 = processString(wordTwo, n);
	System.out.println("second results has " + res2.size());
        displayResult(res2);

        int c = common(method, res1,res2);
	System.out.println("common is " + c);
        int u = union(method, res1,res2);
	System.out.println("union is " + u);
        double sim = (double)c/(double)u;

        return sim;
    }

    public static int common(int method, List<NgramResult> One, List<NgramResult> Two)
    {
        int res = 0;

        for (int i = 0; i < One.size(); i++)
        {
            for (int j = 0; j < Two.size(); j++)
            {
		//System.out.println("comparing " + One.get(i).theWord + " and " + Two.get(j).theWord);

                if (One.get(i).theWord.equalsIgnoreCase(Two.get(j).theWord)) {

			switch ( method ) {
				case 1:
					res += Two.get(j).theCount;
					break;
			//res += (One.get(i).theCount + Two.get(j).theCount);
				case 2:
					if ( One.get(i).theCount > Two.get(j).theCount )
						res += One.get(i).theCount;
					else
						res += Two.get(j).theCount;
					break;
			}
		}
            }
        }

        return res;
    }

    public static int union(int method, List<NgramResult> One, List<NgramResult> Two)
    {

        List<NgramResult> t = new ArrayList<NgramResult>(); 

	if ( method == 1 ) {
		for(int k=0; k<Two.size(); k++) {
			NgramResult ngramResult = new NgramResult(Two.get(k).theWord, Two.get(k).theCount);
			t.add(ngramResult);
		}
	}

	if ( method == 2 ) {
        	for (int i = 0; i < One.size(); i++)
        	{
            	boolean found = false;
            	for (int j = 0; j < t.size() && !found; j++)
            	{
                	if (One.get(i).theWord.equalsIgnoreCase(t.get(j).theWord))
                	{
                    	found = true;
		    	t.get(j).theCount += One.get(i).theCount;
		    	break;
                	}
            	}
	
            	if (!found)
            	{
                	NgramResult r = new NgramResult(One.get(i).theWord, One.get(i).theCount);
                	t.add(r);
            	}
        	}
	}

	if ( method == 1 ) {
        	int qty = 0;
        	for (int i = 0; i < t.size(); i++)
			qty += t.get(i).theCount;
	
		return qty;
	}
        //return t.size();
	
	if ( method == 2 ) {
		int qty = 0;
		int i;
		for(i=0; i<One.size(); i++) {
			qty += One.get(i).theCount;
			//qty++;
		}
		for(i=0; i<Two.size(); i++) {
			qty += Two.get(i).theCount;
			//qty++;
		}
		return qty;
	}

	return 0;
    }

    public static List<NgramResult> processString(String input, int n)
    {
        List<NgramResult> t = new ArrayList<NgramResult>();
	//System.out.println("input is [[" + input + "]]");

	StringTokenizer toks = new StringTokenizer(input, " ");

	while ( toks.hasMoreTokens() ) {
		String c = toks.nextToken();

		//System.out.println("[" + c + "]");


        	String spacer = "";
        	for (int i = 0; i < n-1; i++) {
            		spacer = spacer + "%";
        	}
        	c = spacer + c + spacer;
	
        	for (int i = 0; i < c.length(); i++) {
            		if (i <= (c.length() - n)) {
				int k;
                		if ( ( k = contains(t, c.substring(i, n+i))) > -1) {
                    			t.get(k).setTheCount(t.get(k).getTheCount()+1);
                		}
                		else {
		    			NgramResult res = new NgramResult(c.substring(i, n+i), 1);
                    			t.add(res);
                		}
            		}
        	}

	}
        return t;
    }

    private static int contains(List<NgramResult> list, String c)
    {
        for (int i = 0; i < list.size(); i++)
        {
            if (list.get(i).theWord.equalsIgnoreCase(c)) {
                return i;
	    }
        }
        return -1;
    }

    public static void displayResult(List<NgramResult> d)
    {
        for (int i = 0; i < d.size(); i++)
        {
            System.out.println(d.get(i).theWord+" occurred "+d.get(i).theCount+" times");
        }
    }

    public static void main(String args[]) {
	try {
		Ngram ngram = new Ngram();
		int n = Integer.parseInt(args[0]);
		//System.out.println("n is " + n);
		double similarity = ngram.getSimilarity(1, args[1], args[2], n);
		long k = Math.round(similarity * 100);
		System.out.println(similarity);

		similarity = ngram.getSimilarity(2, args[1], args[2], n);
		k = Math.round(similarity * 100);
		System.out.println(similarity);
    		//public double getSimilarity(String wordOne, String wordTwo, int n)
		//System.out.println("results size is " + ngram.results.size());
	}
	catch ( Throwable t ) {
		System.out.println("throwing " + t);
	}
    }
}

